문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 하노이의 탑 (문단 편집) == 전설 == [[1883년]] [[프랑스]]의 [[수학자]] 에두아르드 뤼카(Lucas,E. : 1842~1891)가 처음으로 발표한 게임이다. 이후 여러 사람을 거치면서 다음과 같은 [[전설]]이 덧붙여졌다. >고대 [[인도]] [[바라나시|베나레스]]에 있는 한 사원의 이야기 >여기에는 [[다이아몬드]]로 이루어진 3개의 기둥이 있고, 그 기둥 중 하나에 가운데에 구멍이 나 기둥에 끼울 수 있게 된 64개의 크기가 각각 다른 [[황금]] [[원반]]이 꽂혀 있다고 한다. 황금 원반은 가장 아래쪽에 있는 것이 가장 크고 위로 갈수록 점차 작아져 전체적으로 원추형의 탑을 이루고 있는데, 원반은 한 번에 하나씩만 옮길 수 있으며 작은 원반 위에 그보다 더 큰 원반을 옮길 수 없다. >이 규칙으로 64개의 원반을 처음 놓여 있던 막대에서 다른 막대로 모두 옮기면 탑은 무너지고 [[세계멸망|세상의 종말이 온다]]고 한다. 이 가짜 전설 덕분에 [[인도]]에 있는 [[바라나시|베나레스]][* 현재 이름은 [[바라나시]].]가 [[베트남]]의 [[하노이]]와 같은 곳인 줄 아는 사람들이 꽤 많은 듯하다. 이 규칙들을 이용하여 64개의 원반을 다른 막대로 전부 옮기는 것은 간단해 보이지만 '작은 원반 위에 큰 원반을 올릴 수 없다' 는 규칙은 의외로 크게 작용하는데, 이를 지키면서 n개의 원반을 한쪽 기둥에서 다른 쪽으로 옮기는 데 걸리는 최소 횟수가 [math( 2^n - 1 )]번이기 때문이다. [math(n+1)]번째 원반을 목표로 하는 비어있는 한 기둥으로 옮기려면, 우선 그 위의 1번부터 [math(n)]번째까지의 원반을 목표로 하는 기둥 이외의 비어있는 기둥으로 옮겨야만 한다. 이 사실을 이용해서 다음과 같이 1번부터 [math(n+1)]번째까지의 원반을 목표로 하는 기둥으로 옮기는 데 요구되는 원반이동 횟수를 계산할 수 있다. 1부터 [math( n )]번째까지의 원반을 비어있는 한 기둥으로 옮기는 데 필요한 최소 횟수를 [math( a_n )]라고 하자. 1번부터 [math( (n+1) )]번째까지의 원반을 목표로 하는 비어있는 기둥으로 옮기려면 ([math( a_{n+1} )]을 구하려면) [math( n )]번째까지의 원반을 비어있는 다른 기둥으로 옮기고 ([math( a_n )]를 더하고) [math( (n+1) )]번째 원반을 목표로 하는 기둥으로 옮기고 ([math( 1 )]을 더하고) [math( n )]번째까지의 원반을 [math( (n+1) )]번째 원반 위로 옮기면 ([math( a_n )]를 다시 더하면) 된다. 따라서 [math( a_1 = 1, a_{n+1}=2a_n+1 )]이고 이 [[점화식]] (Recursive relation)에 의한 수열 [math( a_n )]의 일반항을 구해보면 [math( a_n=2^n - 1 )]가 나온다.[* 이 수열의 일반항을 구하는 방법은 다음과 같다.[br]관계식 [math( a_{n+1} = 2 a_n + 1)]을 [math( a_{n+1}+1 = 2(a_n+1) )]로 변형하고, [math( b_n=a_n+1 )]이라고 두면 [math( b_{n+1} = 2b_n )]이 되므로 [math( b_n )]는 첫째항이 [math( b_1 = a_1 + 1 = 2 (\because a_1=1))]이고 공비가 [math( 2 )]인 등비수열이 된다. 따라서 [math( b_n = a_n + 1 = 2^{n} )] 이므로 [math( \therefore a_n = 2^{n} - 1 )]이다.] 따라서 64개의 원반을 완전히 옮기는 데 걸리는 횟수는 [math( 2^{64} - 1 )], 자그마치 1844경 6744조 737억 955만 1615회에 달한다. 판을 한 번 옮기는 데 1초가 걸린다 해도 약 5849억년이 걸리는데[* 이 시간은 [[64비트]] 정수형으로 시간을 표기하는 시스템이 한계에 도달하는 데에 필요한 시간과도 같다. 자세한 내용은 [[2038년 문제]] 문서로.], 이는 [[우주]]의 나이인 130~135억년보다도 훨씬 길며 중소형 [[적색왜성]]의 예상 수명과 맞먹는 시간이다. --세계멸망이 오고도 남을 만큼 길다-- 하지만 만약 막대를 하나 더 추가해서 네 개로 만든다면 최소 18,433번만 옮기면 되는데, 1초에 판을 1개 옮긴다 할 때 5시간 7분 13초면 된다. --여전히 오래 걸린다.--[* 사실 기둥이 4개인 하노이 탑 관련 문제는 정말 골 때리는 문제인데, 최소이동경로를 확정할 수가 없기 때문이다. 이유는? 간단하다. 원반이 3개라고 가정하고 첫 번째 원반을 1기둥 -> 4기둥으로 옮긴다고 가정한다.(아무데나 상관이 없다) 그러면 2번째 기둥은? 2번 기둥이나 3번 기둥으로 옮길 수 있게 된다. 즉, 최소 횟수를 위한 이동경로가 한 개가 아니다. 그러면 내가 최소이동횟수를 구해도 "이게 정말 이렇게 옮겼을 때의 최소 이동횟수가 맞나?"라는 질문에 대답을 할 수가 없다.(심지어 이건 아직 증명되지도 않았다.) 원반이 3개면 그게 뭐가 어렵나고 할 수 있지만 우리가 원하는 것은 3개가 아닌 100개, 1000개, 나아가 n개의 원반에서 이동 횟수, 즉 일반항을 구하는 것이 궁극적 목표인데, 거의 논문 하나가 나올 정도로 어렵기에 그냥 논문을 참조하는 것을 추천한다.(논문에서조차 증명은 없다. 그냥 점화식을 구하고 점화식을 토대로 일반항만 구했지, 이게 정말 최소횟수인지 증명하는 내용은 없다.)]저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기